/**
 * @program: LeetCode
 * @description: LeetCode : 34. 在排序数组中查找元素的第一个和最后一个位置
 * @author: WXY
 * @create: 2023-02-07 09:44
 * @Version 1.0
 **/
public class Num034_searchRange {
    public static int[] searchRange1(int[] nums, int target) {
        int left = searchLeftRange(nums, target);
        int right = searchRightRange(nums, target);
        if (right == -2 || left == -2) return new int[]{-1, -1};
        if (right - left > 1) return new int[]{left + 1, right - 1};
        return new int[]{-1, -1};
    }

    private static int searchRightRange(int[] nums, int target) {
        int L = 0;
        int R = nums.length - 1;
        int mid = 0;
        int range = -2;
        while (L <= R) {
            mid = (L + R) / 2;
            if (nums[mid] <= target) {
                L = mid + 1;
                range = L;
            } else if (nums[mid] > target) {
                R = mid - 1;
            }
        }
        return range;
    }

    private static int searchLeftRange(int[] nums, int target) {
        int L = 0;
        int R = nums.length - 1;
        int mid = 0;
        int range = -2;
        while (L <= R) {
            mid = (L + R) / 2;
            if (nums[mid] < target) {
                L = mid + 1;
            } else if (nums[mid] >= target) {
                R = mid - 1;
                range = R;
            }
        }
        return range;
    }

    public static int[] searchRange(int[] nums, int target) {
        int[] ans = new int[]{-1, -1};
        ans[0] = range(nums, target, true);
        ans[1] = range(nums, target, false);
        return ans;
    }

    private static int range(int[] arr, int aim, boolean leftOrRight) {
        int ans = -1;
        int left = 0;
        int right = arr.length - 1;
        int mid = 0;
        while (left <= right) {
            mid = left + (right - left) / 2;
            if (arr[mid] > aim) {
                right = mid - 1;
            } else if (arr[mid] < aim) {
                left = mid + 1;
            } else {
                ans = mid;
                if (leftOrRight) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        int[] arr = {1, 7, 8, 9, 9, 10, 11};
        int aim = 9;
        int ans[] = searchRange(arr, aim);
        int left = ans[0], right = ans[1];
        System.out.println("left = " + left + ";  right = " + right);
        System.out.println(ans);
    }
}
